{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Flood Fill"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: floodFill"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #图像渲染"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一幅以&nbsp;<code>m x n</code>&nbsp;的二维整数数组表示的图画&nbsp;<code>image</code>&nbsp;，其中&nbsp;<code>image[i][j]</code>&nbsp;表示该图画的像素值大小。</p>\n",
    "\n",
    "<p>你也被给予三个整数 <code>sr</code> ,&nbsp; <code>sc</code> 和 <code>newColor</code> 。你应该从像素&nbsp;<code>image[sr][sc]</code>&nbsp;开始对图像进行 上色<strong>填充</strong> 。</p>\n",
    "\n",
    "<p>为了完成<strong> 上色工作</strong> ，从初始像素开始，记录初始坐标的 <strong>上下左右四个方向上</strong> 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 <strong>四个方向上</strong> 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为&nbsp;<code>newColor</code>&nbsp;。</p>\n",
    "\n",
    "<p>最后返回 <em>经过上色渲染后的图像&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/01/flood1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2\n",
    "<strong>输出:</strong> [[2,2,2],[2,2,0],[2,0,1]]\n",
    "<strong>解析:</strong> 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。\n",
    "注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2\n",
    "<strong>输出:</strong> [[2,2,2],[2,2,2]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == image.length</code></li>\n",
    "\t<li><code>n == image[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;= image[i][j], newColor &lt; 2<sup>16</sup></code></li>\n",
    "\t<li><code>0 &lt;= sr &lt;&nbsp;m</code></li>\n",
    "\t<li><code>0 &lt;= sc &lt;&nbsp;n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [flood-fill](https://leetcode.cn/problems/flood-fill/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [flood-fill](https://leetcode.cn/problems/flood-fill/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1],[1,1,0],[1,0,1]]\\n1\\n1\\n2', '[[0,0,0],[0,0,0]]\\n0\\n0\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        R, C = len(image), len(image[0])\n",
    "        color = image[sr][sc]\n",
    "        if color == newColor: return image\n",
    "        def dfs(r, c):\n",
    "            if image[r][c] == color:\n",
    "                image[r][c] = newColor\n",
    "                if r >= 1: dfs(r-1, c)\n",
    "                if r+1 < R: dfs(r+1, c)\n",
    "                if c >= 1: dfs(r, c-1)\n",
    "                if c+1 < C: dfs(r, c+1)\n",
    "\n",
    "        dfs(sr, sc)\n",
    "        return image\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image, sr, sc, newColor):\n",
    "        \"\"\"\n",
    "        :type image: List[List[int]]\n",
    "        :type sr: int\n",
    "        :type sc: int\n",
    "        :type newColor: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        color = image[sr][sc]\n",
    "        a = len(image)\n",
    "        b = len(image[0])\n",
    "        s = [(sr, sc)]\n",
    "        visited = set()\n",
    "        visited.add((sr, sc))\n",
    "        while s:\n",
    "            r, c = s.pop()\n",
    "            image[r][c] = newColor\n",
    "            for (x, y) in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:\n",
    "                if 0<=x<a and 0<=y<b and ((x,y) not in visited) and image[x][y]==color:\n",
    "                    s.append((x, y))\n",
    "                    visited.add((x, y))\n",
    "        return image\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image, sr, sc, newColor, flg=None):\n",
    "        \"\"\"\n",
    "        :type image: List[List[int]]\n",
    "        :type sr: int\n",
    "        :type sc: int\n",
    "        :type newColor: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not flg:\n",
    "            flg = [[0]*len(image[0]) for _ in range(len(image))]\n",
    "        ori = image[sr][sc]\n",
    "        image[sr][sc] = newColor\n",
    "        flg[sr][sc] = 1\n",
    "        for i in range(max(0, sr-1), min(sr+2, len(image))):\n",
    "            if i == sr:\n",
    "                continue\n",
    "            if image[i][sc] == ori and flg[i][sc] != 1:\n",
    "                flg[i][sc] = 1\n",
    "                image = self.floodFill(image, i, sc, newColor, flg)\n",
    "        for i in range(max(0, sc-1), min(sc+2, len(image[0]))):\n",
    "            if i == sc:\n",
    "                continue\n",
    "            if image[sr][i] == ori and flg[sr][i] != 1:\n",
    "                flg[sr][i] = 1\n",
    "                image = self.floodFill(image, sr, i, newColor, flg)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image, sr, sc, newColor):\n",
    "        \"\"\"\n",
    "        :type image: List[List[int]]\n",
    "        :type sr: int\n",
    "        :type sc: int\n",
    "        :type newColor: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        R, C = len(image), len(image[0])\n",
    "        color = image[sr][sc]\n",
    "        if color == newColor:\n",
    "            return image\n",
    "        def dfs(r, c):\n",
    "            if image[r][c] == color:\n",
    "                image[r][c]= newColor\n",
    "                if r >= 1:\n",
    "                    dfs(r-1, c)\n",
    "                if r+1 < R:\n",
    "                    dfs(r+1, c)\n",
    "                if c >= 1:\n",
    "                    dfs(r, c-1)\n",
    "                if c + 1 < C:\n",
    "                    dfs(r, c+1)\n",
    "        dfs(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image, sr, sc, newColor):\n",
    "        \"\"\"\n",
    "        :type image: List[List[int]]\n",
    "        :type sr: int\n",
    "        :type sc: int\n",
    "        :type newColor: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def recurse(sr, sc):\n",
    "            if sr < 0 or sr > len(image) - 1 or sc < 0 or sc > len(image[0]) - 1:\n",
    "                return\n",
    "            if image[sr][sc] == newColor:\n",
    "                return\n",
    "            if image[sr][sc] == old_color:\n",
    "                image[sr][sc] = newColor\n",
    "                recurse(sr - 1, sc)\n",
    "                recurse(sr + 1, sc)\n",
    "                recurse(sr, sc - 1)\n",
    "                recurse(sr, sc + 1)\n",
    "\n",
    "        old_color = image[sr][sc]\n",
    "        recurse(sr, sc)\n",
    "        return image\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image, sr, sc, newColor):\n",
    "        \"\"\"\n",
    "        :type image: List[List[int]]\n",
    "        :type sr: int\n",
    "        :type sc: int\n",
    "        :type newColor: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        oldColor = image[sr][sc]\n",
    "        m,n=len(image),len(image[0])        \n",
    "        def color(sr,sc):\n",
    "            if sr<0 or sr>m-1 or sc<0 or sc>n-1:\n",
    "                return\n",
    "            if image[sr][sc]==newColor:\n",
    "                return\n",
    "            if image[sr][sc]==oldColor:\n",
    "                image[sr][sc]=newColor\n",
    "                color(sr-1,sc)\n",
    "                color(sr+1,sc)\n",
    "                color(sr,sc-1)\n",
    "                color(sr,sc+1)            \n",
    "        color(sr,sc)\n",
    "        return image\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        if image[sr][sc] != newColor:\n",
    "            old, image[sr][sc], m, n = image[sr][sc], newColor, len(image), len(image[0])\n",
    "            for i, j in zip((sr, sr+1, sr, sr-1), (sc+1, sc, sc-1, sc)):\n",
    "                if 0 <= i < m and 0 <= j < n and image[i][j] == old:\n",
    "                    self.floodFill(image, i, j, newColor)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        L = len(image)\n",
    "        R = len(image[1])\n",
    "        if newColor == image[sr][sc]:\n",
    "            return image\n",
    "        else:\n",
    "            def dfs(image,i,j,newColor,former):\n",
    "                if i >= L or j >= R or i < 0 or j < 0:\n",
    "                    return \n",
    "                if image[i][j] == former:\n",
    "                    image[i][j] = newColor\n",
    "                    dfs (image, i+1, j, newColor, former)\n",
    "                    dfs (image, i, j+1, newColor, former)\n",
    "                    dfs (image, i-1, j, newColor, former)\n",
    "                    dfs (image, i, j-1, newColor, former)\n",
    "                return image\n",
    "            return dfs(image, sr, sc,newColor,image[sr][sc])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: list, sr: int, sc: int, newColor: int) -> list:\n",
    "        isJudge = [([0] * len(image[0])) for i in range(len(image))]\n",
    "        self.dfs(image, sr, sc, image[sr][sc], newColor, isJudge)\n",
    "        return image\n",
    "\n",
    "    def dfs(self, image, r, c, oldColor, newColor, isJudge):\n",
    "        nr = len(image)\n",
    "        nc = len(image[0])\n",
    "        if r < 0 or c < 0 or r >= nr or c >= nc or image[r][c] != oldColor or isJudge[r][c] == 1:\n",
    "            return\n",
    "        image[r][c] = newColor\n",
    "        isJudge[r][c] = 1\n",
    "        self.dfs(image, r - 1, c, oldColor, newColor, isJudge)\n",
    "        self.dfs(image, r + 1, c, oldColor, newColor, isJudge)\n",
    "        self.dfs(image, r, c - 1, oldColor, newColor, isJudge)\n",
    "        self.dfs(image, r, c + 1, oldColor, newColor, isJudge)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        \n",
    "        m, n = len(image), len(image[0])\n",
    "        \n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        \n",
    "        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        \n",
    "        start_color = image[sr][sc]\n",
    "        \n",
    "        queue = []\n",
    "        queue.append((sr, sc))\n",
    "        dp[sr][sc] = True\n",
    "        image[sr][sc] = newColor\n",
    "        \n",
    "        while queue:\n",
    "            x, y = queue.pop(0)\n",
    "            \n",
    "            for d in direct:\n",
    "                new_x, new_y = x + d[0], y + d[1]\n",
    "                if 0 <= new_x < m and 0 <= new_y < n and image[new_x][new_y] == start_color and dp[new_x][new_y] == False:\n",
    "                    image[new_x][new_y] = newColor\n",
    "                    dp[new_x][new_y] = True\n",
    "                    queue.append((new_x, new_y))\n",
    "        \n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        oldColor=image[sr][sc]\n",
    "        def dfs(image,x,y,newColor,oldColor):\n",
    "            if x<0 or x>=len(image) or y<0 or y>=len(image[0]):\n",
    "                return\n",
    "            if image[x][y] != oldColor or image[x][y]==newColor:\n",
    "                return\n",
    "            image[x][y]=newColor\n",
    "            dfs(image,x-1,y,newColor,oldColor)\n",
    "            dfs(image,x+1,y,newColor,oldColor)\n",
    "            dfs(image,x,y-1,newColor,oldColor)\n",
    "            dfs(image,x,y+1,newColor,oldColor)\n",
    "        dfs(image,sr,sc,newColor,oldColor)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        def dfs(cr, cc, image, srcColor, newColor, visited, moves):\n",
    "            #渲染为原始颜色的目前位置以及周围符合条件的未被渲染的像素\n",
    "            if image[cr][cc] != srcColor:\n",
    "                visited.add((cr, cc))\n",
    "                return \n",
    "            else:\n",
    "                image[cr][cc] = newColor \n",
    "                visited.add((cr, cc))\n",
    "            \n",
    "            for addr, addc in moves:\n",
    "                newr = cr + addr \n",
    "                newc = cc + addc \n",
    "                if newr < 0 or newr >= len(image):\n",
    "                    continue \n",
    "                if newc < 0 or newc >= len(image[0]):\n",
    "                    continue \n",
    "                if (newr, newc) in visited:\n",
    "                    continue \n",
    "                dfs(newr, newc, image, srcColor, newColor, visited, moves)\n",
    "\n",
    "        visited = set()\n",
    "        srcColor = image[sr][sc]\n",
    "        dfs(sr, sc, image, srcColor, newColor, visited, [[0, 1], [0, -1], [1, 0], [-1, 0]])\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#######################################################################\n",
    "## kongconf 2020-12-10\n",
    "#######################################################################\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        def dfs(image, sr, sc, oldColor, newColor):\n",
    "            if image[sr][sc] == oldColor:\n",
    "                image[sr][sc] = newColor\n",
    "            else:\n",
    "                return\n",
    "            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                x, y = sr + dx, sc + dy\n",
    "                if 0 <= x < len(image) and 0 <= y < len(image[0]):\n",
    "                    dfs(image, x, y, oldColor, newColor)\n",
    "        if image[sr][sc] != newColor:\n",
    "            dfs(image, sr, sc, image[sr][sc], newColor)\n",
    "        return image\n",
    "#######################################################################"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        if not image or newColor == image[sr][sc]: return image\n",
    "        nr = len(image)\n",
    "        nc = len(image[0])\n",
    "        queue = [(sr,sc)]\n",
    "        oldColor = image[sr][sc]\n",
    "        while queue:\n",
    "            r,c = queue.pop()\n",
    "            image[r][c] = newColor\n",
    "            for x, y in [(r-1,c),(r,c+1),(r+1,c),(r,c-1)]:\n",
    "                if 0 <= x < nr and 0 <= y < nc and image[x][y] == oldColor:\n",
    "                    queue.append((x,y))\n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        if newColor==image[sr][sc]:\n",
    "            return image\n",
    "        major=image[sr][sc]\n",
    "        chang=len(image)\n",
    "        kuan=len(image[0])\n",
    "        def dfs(sx,sy):\n",
    "            image[sx][sy]=newColor\n",
    "            if chang-1>=sx+1>=0 and image[sx+1][sy]==major:\n",
    "                dfs(sx+1,sy)\n",
    "            if chang-1>=sx-1>=0 and image[sx-1][sy]==major:\n",
    "                dfs(sx-1,sy)\n",
    "            if kuan-1>=sy+1>=0 and image[sx][sy+1]==major:\n",
    "                dfs(sx,sy+1)\n",
    "            if kuan-1>=sy-1>=0 and image[sx][sy-1]==major:\n",
    "                dfs(sx,sy-1)\n",
    "        \n",
    "        dfs(sr,sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def floodFill(self, image, sr, sc, newColor):\n",
    "        \"\"\"\n",
    "        :type image: List[List[int]]\n",
    "        :type sr: int\n",
    "        :type sc: int\n",
    "        :type newColor: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        rl = len(image)\n",
    "        cl = len(image[0])\n",
    "        bimage = [[False for _ in range(cl)] for _ in range(rl)]\n",
    "\n",
    "        def dfs(sr, sc, newColor, oldColor):\n",
    "            if bimage[sr][sc]:\n",
    "                return\n",
    "            bimage[sr][sc] = True\n",
    "            if sr - 1 >= 0 and image[sr - 1][sc] == oldColor:\n",
    "                dfs(sr - 1, sc, newColor, oldColor)\n",
    "            if sr + 1 < rl and image[sr + 1][sc] == oldColor:\n",
    "                dfs(sr + 1, sc, newColor, oldColor)\n",
    "            if sc + 1 < cl and image[sr][sc + 1] == oldColor:\n",
    "                dfs(sr, sc + 1, newColor, oldColor)\n",
    "            if sc - 1 >= 0 and image[sr][sc - 1] == oldColor:\n",
    "                dfs(sr, sc - 1, newColor, oldColor)\n",
    "            image[sr][sc] = newColor\n",
    "        dfs(sr, sc, newColor, image[sr][sc])\n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        if len(image) == 0 or len(image[0]) == 0:\n",
    "            return image\n",
    "\n",
    "        flag = image[sr][sc]\n",
    "        if flag == newColor:\n",
    "            return image\n",
    "        image[sr][sc] = newColor\n",
    "\n",
    "        queue = [(sr, sc)]\n",
    "        xs = [1, -1, 0, 0]\n",
    "        ys = [0, 0, 1, -1]\n",
    "        while queue:\n",
    "            px, py = queue.pop(0)\n",
    "            for (x, y) in zip(xs, ys):\n",
    "                nx, ny = px + x, py + y\n",
    "                if nx < 0 or nx >= len(image) or ny < 0 or ny >= len(image[0]) or image[nx][ny] != flag:\n",
    "                    continue\n",
    "                image[nx][ny] = newColor\n",
    "                queue.append((nx, ny))\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 使用递归实现\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:    \n",
    "        currColor = image[sr][sc]\n",
    "        if currColor == newColor:\n",
    "            return image\n",
    "        \n",
    "        m,n = len(image),len(image[0])\n",
    "        query = collections.deque([(sr,sc)])\n",
    "        image[sr][sc] = newColor\n",
    "        \n",
    "        while query:\n",
    "            x,y = query.popleft()\n",
    "            alist = zip((x,x,x-1,x+1),(y-1,y+1,y,y))\n",
    "            for newx,newy in alist:\n",
    "                # 只有上下左右位置上的值与初始位置相同时才做改变\n",
    "                if 0<=newx<m and 0<=newy<n and image[newx][newy] == currColor:\n",
    "                    query.append((newx,newy))\n",
    "                    image[newx][newy] = newColor\n",
    "        return image\n",
    "                    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:\n",
    "        dirs = [[0, 1], [1, 0], [-1, 0], [0, -1]]\n",
    "        q = collections.deque([(sr, sc)])\n",
    "        old_color = image[sr][sc]\n",
    "        image[sr][sc] = color\n",
    "        while q:\n",
    "            cur_x, cur_y = q.popleft()\n",
    "            image[cur_x][cur_y] = color\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = cur_x + dx, cur_y + dy\n",
    "                if nx < 0 or nx >= len(image) or ny < 0 or ny >= len(image[0]) or image[nx][ny] != old_color or image[nx][ny] == color:\n",
    "                    continue\n",
    "                q.append((nx, ny))\n",
    "        return image\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:\n",
    "        row = len(image)\n",
    "        col = len(image[0])\n",
    "        s = image[sr][sc]\n",
    "        if s == color:\n",
    "            return image\n",
    "        def helper(a,b):\n",
    "            if a in {-1,row} or b in {-1,col} or image[a][b] != s or image[a][b] == color:\n",
    "                return\n",
    "            image[a][b] = color\n",
    "            helper(a-1,b)\n",
    "            helper(a,b-1)\n",
    "            helper(a+1,b)\n",
    "            helper(a,b+1)\n",
    "            return image\n",
    "        return helper(sr,sc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:\n",
    "        origin_color = image[sr][sc]\n",
    "        if origin_color == color:\n",
    "            return image\n",
    "        def myfunc(i, j):\n",
    "            if 0 <= i < len(image) and 0 <= j < len(image[0]):\n",
    "                if image[i][j] == origin_color:\n",
    "                    image[i][j] = color\n",
    "                    myfunc(i+1, j)\n",
    "                    myfunc(i-1, j)\n",
    "                    myfunc(i, j+1)\n",
    "                    myfunc(i, j-1)\n",
    "        myfunc(sr, sc)\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:\n",
    "        image = copy.deepcopy(image)\n",
    "        m,n = len(image), len(image[0])\n",
    "        old_color = image[sr][sc]\n",
    "        seen = set()\n",
    "        def dfs(x,y):\n",
    "            image[y][x] = color\n",
    "            seen.add((x,y))\n",
    "            for dx, dy in [(0,-1), (0,1), (-1,0), (1,0)]:\n",
    "                nx = x + dx\n",
    "                ny = y + dy\n",
    "                if 0<=nx<n and 0<=ny<m and image[ny][nx] == old_color and (nx,ny) not in seen:\n",
    "                    dfs(nx,ny)\n",
    "        dfs(sc,sr)\n",
    "        return image\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:\n",
    "        if image[sr][sc] == newColor:\n",
    "            return image\n",
    "        stack = [(sr,sc)]\n",
    "        old = image[sr][sc]\n",
    "        directions = {(0,1),(0,-1),(-1,0),(1,0)}\n",
    "        while stack:\n",
    "            [i, j]= stack.pop()\n",
    "            image[i][j] = newColor \n",
    "            for dir in directions:\n",
    "                new_i = i + dir[0]\n",
    "                new_j = j + dir[1]\n",
    "                if 0<= new_i < len(image) and  0<= new_j < len(image[0]) and image[new_i][new_j] == old:\n",
    "                    stack.append((new_i, new_j))\n",
    "                    image[new_i][new_j] = newColor\n",
    "        return image\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:\n",
    "        q = deque()\n",
    "        q.append((sr, sc))\n",
    "        old = image[sr][sc]\n",
    "        m, n = len(image), len(image[0])\n",
    "        if color == image[sr][sc]:\n",
    "            return image\n",
    "        while len(q) > 0:\n",
    "            node = q.popleft()\n",
    "            image[node[0]][node[1]] = color\n",
    "            for a, b in pairwise((0, 1, 0, -1, 0)):\n",
    "                if 0 <= node[0] + a < m and 0 <= node[1] + b < n and image[node[0] + a][node[1] + b] == old:\n",
    "                    q.append((node[0] + a, node[1] + b))\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:\n",
    "        currColor=image[sr][sc]\n",
    "        if currColor==color:\n",
    "            return image\n",
    "        \n",
    "        m,n=len(image),len(image[0])\n",
    "        que=collections.deque([(sr,sc)])\n",
    "        image[sr][sc]=color\n",
    "        while que:\n",
    "            x,y=que.popleft()\n",
    "            for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "                mx,my=x+dx,y+dy\n",
    "                if 0<=mx<m and 0<=my<n and image[mx][my]==currColor:\n",
    "                    que.append((mx,my))\n",
    "                    image[mx][my]=color\n",
    "        return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:\n",
    "        m=len(image)\n",
    "        n=len(image[0])\n",
    "        q=deque([(sr,sc)])\n",
    "        ori=image[sr][sc]\n",
    "        if ori==color:\n",
    "            return image\n",
    "        image[sr][sc]=color\n",
    "        while q:\n",
    "            i,j=q.popleft()\n",
    "            for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                if 0<=ni<m and 0<=nj<n and image[ni][nj]==ori:\n",
    "                    q.append((ni,nj))\n",
    "                    image[ni][nj]=color\n",
    "        return image"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
